#include "binary_tree.h"
#include <stdio.h>
#include <stdlib.h>

//change tree to double link
NodePtr binary_tree_to_double_link(TreeRoot root, bool right)
{
	if (NULL == root) {
		return NULL;
	}
	if (root->left) {
		root->left = binary_tree_to_double_link(root->left, false);
		root->left->right = root;
	}
	if (root->right) {
		root->right = binary_tree_to_double_link(root->right, true);
		root->right->left = root;
	}
	if (right) {
		while (root->left) {
			root = root->left;
		}
	}
	else {
		while (root->right) {
			root = root->right;
		}
	}
	return root;
}

bool binary_tree_to_double_link(TreeRoot root, NodePtr& last_node)
{
	if (NULL == root) {
		return false;
	}
	if (root->left) {
		binary_tree_to_double_link(root->left, last_node);
	}
	root->left = last_node;
	last_node->right = root;
	last_node = root;
	if (root->right) {
		binary_tree_to_double_link(root->right, last_node);
	}
	return true;
}

/*
int main()
{
	
	TreeRoot root = create_binary_tree(10);
	insert_element_into_binary_tree(root, 6);
	insert_element_into_binary_tree(root, 14);
	insert_element_into_binary_tree(root, 4);
	insert_element_into_binary_tree(root, 8);
	insert_element_into_binary_tree(root, 12);
	insert_element_into_binary_tree(root, 16);
	//insert_element_into_binary_tree(root,);
	preorder_print_binary_tree(root);
	printf("\n");
	root = binary_tree_to_double_link(root, true);
	while (root) {
		printf("%d ", root->e);
		root = root->right;
	}
	printf("\n");
	
	
}
*/
